home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
vol_200
/
289_01
/
othello.h
< prev
next >
Wrap
Text File
|
1989-05-23
|
14KB
|
359 lines
/*-----------------------------------------------------------------------------
OTHELLO.H
This file contains global function prototypes, external variable declarations,
and manifest constant definitions for the othello program.
Revision History
----------------
Jon Ward 17 Oct 1988 Initial Revision.
Jon Ward 30 Oct 1988 Added typedef for move type.
Jon Ward 01 Nov 1988 Added constant defs and macros.
Jon Ward 04 Dec 1988 Changed fa_ndx_struct from a structure to an
array.
Jon Ward 12 Dec 1988 Started adding function prototypes and external
declarations for global variables.
Gary Culp 15 Dec 1988 Added declaration for delta_array, BELONGS macro.
Gary Culp 19 Dec 1988 Updated prototypes for functions in PROTECT.C
Gary Culp 22 Dec 1988 Added MAX_AFFECTED_PIECES.
Gary Culp 2 Jan 1989 Added STATIC and BT_MAX_DEPTH
Jon Ward 3 Jan 1989 Added prototypes for minimax functions.
added prototype for limb removing DB function
Jon Ward 7 Jan 1989 Added last_max_score extern for MINIMAX.C.
-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------
For debugging purposes, it is sometimes useful to change 'static' functions and
variables to global, so they will appear in MAP files. This definition makes
that easier to do. Just define STATIC to be an empty string (For MSC, the
command line option "/DSTATIC=" will do this.) Do not use STATIC to declare
static variables inside functions! They will turn into automatics, and cease
to work correctly.
-----------------------------------------------------------------------------*/
#ifndef STATIC
#define STATIC static
#endif
/*-----------------------------------------------------------------------------
This constant represents the number of axes on the othello board that can
contain a capture. There are obviously 8 vertical and 8 horizontal columns and
rows. There are also 15 diagonal "rows" forward and 15 diagonal "rows"
backward. However, 4 of each of these 15 are eliminated because a row must
contain 3 or more cells for a capture to occur. The 2 diagonal "rows" nearest
each corner have only 1 and 2 cells.
-----------------------------------------------------------------------------*/
#define NUM_CAPTURABLE_AXES (11 + 11 + 8 + 8)
/*-----------------------------------------------------------------------------
The following board structure will contain the definition for a particular
board.
The board element will contain bits (as defined below) that tell whether a cell
is empty or occupied and whether the piece in that cell is protected along an
axis. Once a piece is protected along all 4 axes, it has become permanent and
can never be changed in the remainder of this game.
The fa_bits (fa being full axis) is an array of bits that tell if a particular
axis is completely full. 1 is added for the non-capturable axes and 7 is added
to round up to the nearest byte.
-----------------------------------------------------------------------------*/
#define FA_BITS_SIZE ((NUM_CAPTURABLE_AXES + 1 + 7) / 8)
struct board_struct
{
unsigned char board [10][10];
unsigned char fa_bits [FA_BITS_SIZE];
};
typedef struct board_struct board_type;
/*-----------------------------------------------------------------------------
Board manifest constants and macros for the board_struct board element.
Note that the first four bits (NO_PIECE thru OFF_BOARD) are mutually exclusive.
Only one of them may be set at a given time.
This bit mapping is NOT arbitrary. The IS_PERM macro is a good example of why
it is not. The program exploits the numerical properties of the variables
built with these definitions, as well as extracting bits from them.
-----------------------------------------------------------------------------*/
#define NO_PIECE 0x01 /* Empty cell, No disk there */
#define US_PIECE 0x02 /* Cell occupied by our disk */
#define THEM_PIECE 0x04 /* Cell occupied by their disk */
#define OFF_BOARD 0x08 /* Cell is off the board */
#define BD_AX 0x10 /* Backward diagonal axis protected */
#define FD_AX 0x20 /* Forward diagonal axis protected */
#define H_AX 0x40 /* Horizontal axis protected */
#define V_AX 0x80 /* Vertical axis protected */
#define IS_PERM(cell) ((cell) > (NO_PIECE | BD_AX | FD_AX | H_AX | V_AX))
#define BELONGS(cell,code) ((cell)&(code))
#define TEST_BITS(cell,bits) ((cell) & (bits))
#define SET_BITS(cell,bits) ((cell) |= (bits))
#define CLR_BITS(cell,bits) ((cell) &= ~(bits))
/*-----------------------------------------------------------------------------
Full axis table for FA index table and macros for setting and testing the FA
bits.
-----------------------------------------------------------------------------*/
typedef unsigned char fa_type [4];
#define BD_NDX 0 /* index for backward diagonal FA bit */
#define FD_NDX 1 /* index for forward diagonal FA bit */
#define H_NDX 2 /* index for horizontal FA bit */
#define V_NDX 3 /* index for vertical FA bit */
#define WHICH_BYTE(ndx) ((unsigned char) (ndx) >> 3)
#define BIT_N_BYTE(ndx) ((unsigned char) 1 << ((ndx) & 0x07))
#define SET_FA_BIT(fa,bit) ((fa) [WHICH_BYTE(bit)] |= BIT_N_BYTE(bit))
#define CHK_FA_BIT(fa,bit) ((fa) [WHICH_BYTE(bit)] & BIT_N_BYTE(bit))
/*-----------------------------------------------------------------------------
The following type is used to represent a number used for indexing into the
database manager when referencing a node (limb) in one of the move trees.
-----------------------------------------------------------------------------*/
typedef unsigned int key_type;
#define NO_KEY ((key_type) 0xFFFF)
/*-----------------------------------------------------------------------------
The following type is used to represent the row and column of an othello move.
Since there are only 8 rows and 8 columns on the othello board, the move can be
reduced to 6 bits, 3 for the row and 3 for the column. One of the remaining
bits is used to indicate that the player (computer or opponent) has no valid
moves. The other bit will be used by the DBM to indicate that there is a board
associated with a limb entry.
The GET_ROW/GET_COL macros extract and normalize the row and col stored in a
move_type.
The SET_ROW/SET_COL macros initialize the row and col for a move_type.
The CLR_ROW/CLR_COL macros clear the row and col for a move_type.
-----------------------------------------------------------------------------*/
typedef unsigned char move_type;
#define ROW_MASK 0x07 /* 3 bits for row number */
#define COL_MASK 0x38 /* 3 bits for col number */
#define NO_MOVE_MASK 0x40 /* bit set for no valid moves */
#define BOARD_MASK 0x80 /* bit set in DBM if bottom level of tree */
#define HASNT_MOVED BOARD_MASK /* returned by check_for_input() when
move has not been entered yet */
#define GET_ROW(move) ((move) & ROW_MASK)
#define GET_COL(move) (((move) & COL_MASK) >> 3)
#define SET_ROW(move,row) ((move) |= ((row) & 0x07))
#define SET_COL(move,col) ((move) |= ((col) & 0x07) << 3)
#define CLR_ROW(move) ((move) &= ~ROW_MASK)
#define CLR_COL(move) ((move) &= ~COL_MASK)
#define SET_ROW_COL(m,r,c) ((m) |= (((c) & 0x07) << 3) | ((r) & 0x07))
/*-----------------------------------------------------------------------------
The limb_type type represents the data that is contained at each branch (limb)
in the move tree.
The bc union is either a key for the board at this limb, or is a key for the
first child of this limb. The move struct element will have the BOARD_MASK
bit set if the bc element is a board key. If the BOARD_MASK bit is NOT set,
bc will be the child_key.
A value of NO_KEY indicates that there are no children or siblings.
-----------------------------------------------------------------------------*/
struct limb_struct
{
move_type move; /* w